package algorithm;

public class leetcode_0279 {
    public int numSquares(int n) {
        int [] point=new int[100];
        for(int i=0;i<100;++i){
            point[i]=(i+1)*(i+1);
        }
        int[] dp=new int[n+1];
        for(int i=1;i<n+1;++i){
            dp[i]=100000;
        }
        for(int i=1;i<n+1;++i){
            for(int j=0;j<100;++j){
                if(i>=point[j]) dp[i]=Math.min(dp[i],dp[i-point[j]]+1);
            }
        }
        return dp[n];
    }
}
